Field
The present disclosure relates to a method and an apparatus for determining a decoding order for shuffled decoding when low-density parity-check (LDPC) codes are decoded.
Description of the Related Art
An LDPC code is a linear block code suggested by Gallager and also an error correcting code which has an excellent error correcting capability close to a channel capacity suggested by Shannon. The LDPC code has been adopted as standards in various broadcast and wireless LAN technologies such as ATSC 3.0 or IEEE 802.11 and is broadly used for error correction in various storage devices including a flash memory.
The LDPC code restores a message through iterative decoding and each LDPC code is characterized by a parity check matrix. The parity check matrix may be represented by a Tanner graph. The Tanner graph is formed by variable nodes, check nodes, and edges showing the connection therebetween.
Such an LDPC decoder repeatedly performs an operation of information exchanged between the variable nodes and the check nodes which are connected to each other and performs the iterative decoding until it reaches a predetermined maximum number of iterations or satisfies a parity check equation.
The LDPC decoding is divided into parallel decoding, serial decoding, and partial-parallel serial decoding depending on an operating method.
In the parallel decoding, all check nodes simultaneously perform the operation and then all variable nodes simultaneously perform the operation. In the serial decoding, the check nodes or the variable nodes sequentially perform the operation.
Among the serial decodings, an algorithm which sequentially performs operations for the check nodes is layered decoding and an algorithm which sequentially performs operations for the variable nodes is shuffled decoding.
The serial decoding has an advantage in that the number of iterative decoding times required for the same error correcting capability is reduced by half as compared with the parallel decoding, but has a disadvantage in that a time required for one iterative decoding is much longer than that of the parallel decoding so that the entire operating time is longer than that of the parallel decoding.
In order to supplement the above-mentioned disadvantage, a partial-parallel serial decoding technique which divides check nodes or variable nodes into a plurality of groups and simultaneously performs the operation on nodes in the same group and sequentially performs the operation on the groups has been suggested. According to the serial decoding and the partial-parallel serial decoding, the number of iterative decoding times required until the parity check equation is satisfied may vary depending on the operation order of the nodes or the groups.
In the above-described shuffled decoding technique, in order to determine the operation order of the variable nodes, an algorithm which performs the operation in the order from a higher order of variable node to a lower order of variable node in consideration of a degree of the variable node has been proposed in the related art.
However, according to the algorithm which performs the operation in the order from a higher order of variable node to a lower order of variable node in consideration of a degree of the variable node, when a plurality of variable nodes has the same degree, it is difficult to determine the operation order. Further, even though the operation order is determined, a wrong operation order can be determined.